package problem567;

//567.字符串的排列
//https://leetcode.cn/problems/permutation-in-string/

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int[] hash1 = new int[128];
        int[] hash2 = new int[128];
        int count = 0, n = s2.length();
        for (char ch : s1.toCharArray()) {
            if (hash1[ch]++ == 0) {
                count++;
            }
        }

        int size = 0;
        for (int i = 0, j = 0; j < n; j++) {
            char ch = s2.charAt(j);
            hash2[ch]++;
            if (hash2[ch] == hash1[ch]) {
                size++;
            }
            if (j - i + 1 > s1.length()) {
                if (hash2[s2.charAt(i)]-- == hash1[s2.charAt(i)]) {
                    size--;
                }
                i++;
            }
            if (size == count) {
                return true;
            }
        }
        return false;
    }
}